package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         92,
		Discription: "反转部分链表",
		Level:       2,
		Labels: map[string]int{
			"链表": 1,
		},
	})
}

func ReverseBetween(head *ds.ListNode, left int, right int) *ds.ListNode {
	count := 0
	preHead := &ds.ListNode{
		Next: head,
	}
	var leftNode *ds.ListNode

	temp := preHead
	for {
		count++
		if count == left {
			leftNode = temp
			break
		}
		temp = temp.Next
	}

	//记录left:部分链表的前一个节点
	//记录tail：部分链表反转前的第一个节点
	var newHead *ds.ListNode
	temp = temp.Next
	tail := temp
	for {
		count++
		oldHead := newHead
		next := temp.Next
		newHead = temp
		temp.Next = oldHead
		temp = next

		if count > right {
			break
		}
	}

	//记录right:部分链表的后一个节点
	//记录newHead：部分链表反转前的最后一个节点
	rightNode := temp
	leftNode.Next = newHead
	tail.Next = rightNode

	return preHead.Next
}
